package LearnDataStructure.d_图结构.例题;

import java.util.*;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-16 17:08
 * @description: LeetcodeLearnAlgorithm -> 例题
 */
/*
您被指定设计广域中某些点之间的网络连接。
将为您提供区域中的一组点，以及一组可能连接成对点的电缆布线。
对于两点之间的每一条可能布线，都会为您提供连接该布线上的点所需的电缆长度。
请注意，在两个给定点之间可能存在许多可能的路线。假设给定的可能路线（直接或间接）连接该区域中的每两个点。
您的任务是为该区域设计网络，
以便每两点之间都有一个连接（直接或间接）（即，所有点都是互连的，但不一定是通过直接电缆），
并且所用电缆的总长度最小。

输入文件由许多数据集组成。
每个数据集定义一个所需的网络。


集合的第一行包含两个整数：第一个定义给定点的数量P，第二个定义点之间给定路线的数量R。
以下R行定义了点之间的给定路线，
每条线给出三个整数：
前两个数字表示点，
第三个数字表示路线的长度。
数字用空格分隔。


仅给出一个数字P＝0的数据集表示输入的结束。
数据集用空行分隔。

最大点数为50。
给定路线的最大长度为100。
可能的路线数量是无限的。
节点用介于1和P（包括1和P）之间的整数来标识。
两点i和j之间的路线可以给定为i j或j i。



input
1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

output
0
17
16
26
 */
public class a_网络接线byKruskal {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str = "";
        while (!(str = scanner.nextLine()).equals("0")) {//str = scanner.next()是获取点数和边数
            if (str.length() == 0) {
                continue;
            }
            String[] pointNumAndEdgeNum = str.split(" ");
            int pointNum = Integer.parseInt(pointNumAndEdgeNum[0]);
            int edgeNum = Integer.parseInt(pointNumAndEdgeNum[1]);
            if (edgeNum > 0) {
                List<GraphNode_EdgeSet<Integer>> edgeList = new ArrayList<GraphNode_EdgeSet<Integer>>();
                for (int i = 0; i < edgeNum; i++) {
                    edgeList.add(new GraphNode_EdgeSet<Integer>(scanner.nextInt(),scanner.nextInt(),scanner.nextInt()));//获取两个点，两点间的边的权值
                }
                f_Kruskal贪心 helper = new f_Kruskal贪心(edgeList, pointNum);//构造最小生成树
                helper.buildMST();
                // System.out.println();
                System.out.println(helper.weight);//输出最小生成树的最小权值
            } else if (edgeNum == 0) {
                // System.out.println();
                System.out.println(0);
            }
        }
    }

    static class f_Kruskal贪心 {
        //源数据，边集
        public List<GraphNode_EdgeSet<Integer>> edgeList = null;
        //结果，最小生成树的边集
        public Set<GraphNode_EdgeSet<Integer>> treeEdgeList = new HashSet<GraphNode_EdgeSet<Integer>>();
        //帮助map，保存每个边中的“每个点”与“并查集节点”的映射
        public Map<Integer, UnionFindNode> pointAndNode = new HashMap<Integer, UnionFindNode>();
        //总顶点个数
        public int N = 0;
        
        public int weight = 0;
        public UnionFindSet helper = new UnionFindSet();

        public f_Kruskal贪心(List<GraphNode_EdgeSet<Integer>> edgeList, int N) {
            this.edgeList = edgeList;
            this.N = N;
            //为每条边的每个点，与一个并查集的点，建立映射
            for (GraphNode_EdgeSet<Integer> edge : edgeList) {
                pointAndNode.put(edge.start, new UnionFindNode());
                pointAndNode.put(edge.end, new UnionFindNode());
            }
        }

        public Set<GraphNode_EdgeSet<Integer>> getTreeEdgeList() {
            return treeEdgeList;
        }

        public int getWeight() {
            return weight;
        }

        /**
         * 构建最小生成树
         * Kruskal核心语句
         */
        public void buildMST() {
            //先按权值从小到大排序
            Collections.sort(edgeList);
            //迭代，判断每一条边是否可以添加进树边集中
            for (GraphNode_EdgeSet<Integer> edge : edgeList) {
                if (!check(edge)) {
                    continue;
                }
                treeEdgeList.add(edge);
                weight = weight + edge.distance;
                if (treeEdgeList.size() == N - 1) {///满足了，就不需要继续迭代了
                /*
                根据树的定义
                如果边的数量 == 顶点的数量 - 1
                那么就是树，否则就不构成树
                 */
                    return;
                }
            }
        }

        /**
         * 检查这条边的两个点是否都被使用过
         * 如果都没有使用
         * 如果只是用了一个点
         * 就true，同时把这两个点都合并。也就是打上“使用了”的标记
         * @param edge
         * @return
         */
        private boolean check(GraphNode_EdgeSet<Integer> edge) {
            UnionFindNode nodeStart = pointAndNode.get(edge.start);
            UnionFindNode nodeEnd = pointAndNode.get(edge.end);
            if (helper.find(nodeStart) != helper.find(nodeEnd)) {
                helper.union(nodeStart,nodeEnd);
                return true;
            }
            return false;
        }
    }

    static class UnionFindNode{
        public UnionFindNode parent;
    }

    static class UnionFindSet {

        public UnionFindNode find(UnionFindNode source) {
            UnionFindNode node = source;
            HashSet<UnionFindNode> path = new HashSet<UnionFindNode>();
            while (node.parent != null) {//顺着当前节点的父节点，一路找到root
                path.add(node);
                node = node.parent;
            }
            //跳出while后，node就是root
            //下面是重新认父，也就是减小树的高度
            for (UnionFindNode element : path) {//将循环中路过的所有的节点，的父亲，全部改成root
                element.parent = node;
            }
            return node;//root
        }


        public void union(UnionFindNode parent, UnionFindNode child) {
            find(child).parent = parent;
        /*
        find(child)的结果是返回当前并查集的root
        root的parent是null
        把parent当成了root的父节点
        所以说parent成为了新的root
         */
        }
    }

    static class GraphNode_EdgeSet<T> implements Comparable<GraphNode_EdgeSet<T>> {
        public T start = null;
        public T end = null;
        public int distance = 0;

        public GraphNode_EdgeSet(T start, T end, int distance) {
            this.start = start;
            this.end = end;
            this.distance = distance;
        }

        /**
         * 按权值从小到大排序
         * @param other
         * @return
         */
        @Override
        public int compareTo(GraphNode_EdgeSet<T> other) {
            int otherDistance = other.distance;
            int result = 0;
            if (this.distance > otherDistance) {
                result = 1;
            } else if (this.distance < otherDistance) {
                result = -1;
            }
            return result;
        }

        @Override
        public String toString() {
            return start + " -> " + end + " : " + distance;
        }
    }
}
